import java.util.Arrays;

public class Test {
    public static void shellSort(int[] array,int gap) {

        while (gap > 1) {
            gap = gap / 2;
            for (int i = gap; i < array.length; i++) {
                int tmp = array[i];
                int j = i - gap;
                for (; j >= 0; j-=gap) {
                    if (array[j] > tmp) {
                        array[j+gap] = array[j];
                    }else {
                        break;
                    }
                }
                array[j+gap] = tmp;
            }
        }

    }

    public static void main1(String[] args) {
        int[] array = {10,20,8,25,35,6,18,30,5,15,28};
        shellSort(array,5);


    }
    public static void main(String[] args) {
        int[] array = {23,14,25,67,7,9,43,97,32,76};
        //int[] array2 = Arrays.copyOf(array,array.length);

        //直接插入排序
/*        Sort.insertSort(array);
        System.out.println(Arrays.toString(array));*/

        //希尔排序
        Sort.shellSort(array);
        System.out.println(Arrays.toString(array));


        //选择排序
        //Sort.selectSort(array);
        //System.out.println(Arrays.toString(array));

        //堆排序
        //Sort.heapSort(array);
        //System.out.println(Arrays.toString(array));

        //冒泡排序
        //Sort.bubbleSort(array);
        //System.out.println(Arrays.toString(array));

        //快速排序 挖坑法
        //Sort.quickSort(array);
        //System.out.println(Arrays.toString(array));

        //快速排序 Hoare法
        //Sort.quickSortHoare(array);
        //System.out.println(Arrays.toString(array));

        //快速排序 非递归实现
        //Sort.quickSortNor(array);
        //System.out.println(Arrays.toString(array));

        //归并排序 递归实现
        //Sort.mergeSort(array);
        //System.out.println(Arrays.toString(array));

        //归并排序 非递归实现
/*        Sort.mergeSortNor(array);
        System.out.println(Arrays.toString(array));*/

    }
}
